package io.github.handyang.algorithms.graph;


import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

@SuppressWarnings("Duplicates")
public class BFSPaths implements Paths {
    private final Graph graph;

    private final int s;

    private final boolean[] marked;

    private final int[] edgeTo;

    public BFSPaths(Graph graph, int s) {
        this.graph = graph;
        this.s = s;

        this.marked = new boolean[graph.V()];
        this.edgeTo = new int[graph.V()];
        bfs(s);
    }

    private void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            start = queue.poll();
            marked[start] = true;

            for (Integer point : graph.adj(start)) {
                if (marked[point]) continue;

                edgeTo[point] = start;
                marked[point] = true;
                queue.offer(point);
            }
        }
    }

    @Override
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    @Override
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return Collections.emptyList();

        Stack<Integer> res = new Stack<>();
        for (int w = v; w != s; w = edgeTo[w]) {
            res.push(w);
        }
        res.push(s);
        return res;
    }
}
